# Деревья

Формально _дерево_ (_tree_) определяется как конечное множество \\(T\\) одного или более узлов со следующими свойствами:

a) существует один выделенный узел, а именно — _корень_ (_root_) данного дерева \\(T\\);

b) остальные узлы (за исключением корня) распределены среди \\(m \geq 0\\) непересекающихся множеств 
\\(T\_{1},... , T\_{m}\\), и каждое из этих множеств, в свою очередь, является деревом; 
деревья \\(T\_{1},... , T\_{m}\\) называются _поддеревьями_ (_subtrees_) данного корня.

Из этого определения следует, что каждый узел дерева является корнем некоторого поддерева данного дерева. 
Количество поддеревьев узла называется _степенью_ (_degree_) этого узла. 
Узел со степенью нуль называется _концевым узлом_ (_terminal node_) или _листом_ (_leaf_). 
Неконцевой узел называется _узлом ветвления_ (_branch node_).
_Уровень_ (_level_) узла по отношению к дереву T определяется рекурсивно следующим образом. 
Уровень корня дерева T равен нулю, а уровень любого другого узла на единицу выше, 
чем уровень корня ближайшего поддерева дерева T, содержащего данный узел.

Если в п. (b) данного выше определения имеет значение относительный порядок поддеревьев \\(T\_{1},... , T\_{m}\\), 
то дерево является _упорядоченным_ (_ordered tree_). 
Если в упорядоченном дереве \\(m \geq 2\\), то имеет смысл назвать поддерево \\(T\_{2}\\) вторым поддеревом данного корня и т.д. 
Упорядоченные деревья иногда также называются _плоскими деревьями_ (_plane trees_), 
поскольку при их упорядочении имеет значение способ размещения дерева на плоскости. 
Если не считать различными два дерева, которые отличаются только относительным порядком поддеревьев узлов, 
то дерево называется _ориентированным_ (_oriented_), 
поскольку при этом имеет значение только относительная ориентация узлов, а не их порядок. 

_Лес_ (_forest_) — это множество (обычно упорядоченное), не содержащее ни одного непересекающегося дерева 
или содержащее несколько непересекающихся деревьев.
Тогда еще одна формулировка п. (b) в данном выше определении дерева могла бы выглядеть так: 
_узлы дерева при условии исключения корня образуют лес_.

Стандартная терминология древовидных структур происходит от генеалогических деревьев типа "родовой схемы" (наследники человека). 
Каждый узел называется _родителем_ (_parent_) корней его поддеревьев, 
а сами корни называются _братьями-сестрами_ (_siblings_), а также _детьми_ (_children_) своего родителя. 
Корень всего дерева не имеет родителя.

Для обозначения родства, которое может простираться на несколько уровней дерева, 
будут использоваться термины _"предок"_ (_ancestor_) и _"потомок"_ (_descendant_).

> Одним из преимуществ древовидного представления информации является удобство анализа. 
> Когда мы помещаем информацию в древовидную структуру, определенные отношения можно увидеть гораздо быстрее, 
> чем в любом текстовом представлении. 
> Кроме того, деревья обладают определенными свойствами, которые позволяют осуществлять эффективный синтез информации. 

---

**Ссылки:**

- [Donald E. Knuth - The Art of Computer Programming, section 2.3](https://www-cs-faculty.stanford.edu/~knuth/taocp.html)
- [Bhim P. Upadhyaya - Data Structures and Algorithms with Scala](https://link.springer.com/book/10.1007/978-3-030-12561-5)
- [Scalacaster - trees](https://github.com/vkostyukov/scalacaster/tree/master/src/tree)
